/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Mar 13, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a collection of intervals, merge all overlapping
 *              intervals.
 * 
 *              For example, Given [1,3],[2,6],[8,10],[15,18], return
 *              [1,6],[8,10],[15,18].
 */
public class MergeIntervals {

	// Definition for an interval
	private class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}
		
		@Override
		public String toString() {
			return start + " " + end;
		}
	}

	Comparator<Interval> comp = new Comparator<Interval>() {
		
		@Override
		public int compare(Interval o1, Interval o2) {
			if (o1.start < o2.start)
				return -1;
			if (o1.start > o2.start)
				return 1;
			if (o1.end < o2.end)
				return -1;
			if (o1.end > o2.end)
				return 1;
			return 0;
		}
	};
	
	public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
		if (intervals.size() < 2)
			return intervals;
        ArrayList<Interval> res = new ArrayList<Interval>();
        Collections.sort(intervals, comp);
        int s = intervals.get(0).start;
        int e = intervals.get(0).end;
        for (int i = 1; i < intervals.size(); i++) {
        	if (s <= intervals.get(i).start && e >= intervals.get(i).end) {
        		continue;
        	} else if (intervals.get(i).start <= e)
        		e = intervals.get(i).end;
        	else {
        		res.add(new Interval(s, e));
        		s = intervals.get(i).start;
        		e = intervals.get(i).end;
        	}
        }
        res.add(new Interval(s, e));
        
        return res;
    }
	
	@Test
	public void test() {
		ArrayList<Interval> intervals = new ArrayList<Interval>();
		intervals.add(new Interval(1, 4));
		intervals.add(new Interval(2, 3));
		intervals.add(new Interval(8, 10));
		intervals.add(new Interval(15, 18));
		
		for (Interval in : merge(intervals)) {
			System.out.println(in);
		}
	}
}
